import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        HashMap<String,Integer> map1 = new HashMap<>();

        for (String x : words) {
            if (map1.containsKey(x)) {
                map1.put(x, map1.get(x) + 1);
            } else {
                map1.put(x, 1);
            }
        }
        int len = words[0].length();
        for (int i = 0; i < len; i++) {
            int count = 0;
            HashMap<String,Integer> map2 = new HashMap<>();
            for (int left = i,right = i; right+len <= s.length(); right += len) {
                String subStr = s.substring(right,right+ len);
                if (map2.containsKey(subStr)) {
                    map2.put(subStr,map2.get(subStr)+1);
                }else {
                    map2.put(subStr,1);
                }
                if (map1.containsKey(subStr) && map2.get(subStr).compareTo(map1.get(subStr)) <= 0) {
                    count++;
                }

                if (right-left+1 > len * words.length) {
                    String s2 = s.substring(left,left+len);
                    if (map1.containsKey(s2) && map1.get(s2).compareTo(map2.get(s2)) >= 0) {
                        count--;
                    }
                    if (map2.get(s2) > 1) {
                        map2.put(s2,map2.get(s2)-1);
                    }else {
                        map2.remove(s2);
                    }
                    left += len;
                }
                if (count == words.length) {
                    list.add(left);
                }
            }
        }
        return list;
    }
}